package 链表;

/**
 * 部分反转
 * 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
 * User: zhaixiaolong Date:2024/1/8 18:03 ProjectName: algorithm Version:
 */
public class 反转链表2 {

    /**
     * 初始化链表
     *
     * @return
     */
    public static Node initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 4;
        Node node5 = new Node();
        node5.value = 5;
        Node node6 = new Node();
        node6.value = 6;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        return node1;
    }

    public static void main(String[] args) {
        Node head = initData();
        Node newHead = twoIndexPoint(head,2,3);
        System.out.println(newHead.value);
    }

    /**
     * 双指针
     * 1、2、3、4、5、6
     *
     * @param head
     * @return
     */
    public static Node twoIndexPoint(Node head, int left, int right) {
        if (head == null || head.next == null) {
            return head;
        }
        Node headPre = new Node();
        Node headPreTemp = headPre;
        headPre.next = head;
        // 找到前一个节点
        while (headPre.next.value < left) {
            headPre = headPre.next;
        }
        Node revNode = headPre.next;
        Node nextNode = revNode.next;
        while (revNode.value < right){
            Node nextNodeTemp = nextNode.next;
            //反转
            nextNode.next = revNode;
            revNode = nextNode;
            nextNode = nextNodeTemp;
        }
        headPre.next.next = nextNode;
        headPre.next = revNode;
        return headPreTemp.next;
    }
}
